#include <iostream>
#include <vector>
#include <algorithm>
#include "treenode.h"
using namespace std;

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
        if (pre.empty()) {
            return nullptr;
        }
        int pivot = *pre.begin();
        for (auto iter = vin.begin(); iter != vin.end(); ++iter) {
            if (*iter == pivot) {
                TreeNode *node = new TreeNode(pivot);
                node->left = reConstructBinaryTree(vector<int>(pre.begin() + 1, pre.begin() + (iter - vin.begin()) + 1), vector<int>(vin.begin(), iter));
                node->right = reConstructBinaryTree(vector<int>(pre.begin() + (iter - vin.begin()) + 1, pre.end()), vector<int>(iter + 1, vin.end()));
                return node;
            }
        }
        return nullptr;
    }
};

int main() {
    cout << Solution().reConstructBinaryTree({1, 2, 4, 7, 3, 5, 6, 8},  {4, 7, 2, 1, 5, 3, 8, 6}) << endl;
    return 0;
}